With the development of computer technology, the transfer of information in digital form has rapidly increased. In many instances it is necessary that the recipient of a message have a way of discovering whether the message actually came from a particular source, or whether the message was tampered with en route. Such authentication or verification of a message is necessary, for example, in banking applications where it is required that a signed document, such as a bank draft, be authenticated as being actually signed by the indicated signator.
A number of encryption and decryption techniques are readily available to provide some degree of authentication for digital communications. In one such technique, known as a "public key cryptosystem", each user (for example, user A) places in a public file a public key E.sub.A and maintains the secrecy of a corresponding private key D.sub.A. E.sub.A is considered an enciphering, encryption, or encoding key, whereas the private key D.sub.A is considered a corresponding decryption, deciphering or decoding key. E.sub.A and D.sub.A satisfy the equation EQU D.sub.A (E.sub.A (M))=M
for any message M. Furthermore, D.sub.A should not be readily computable from E.sub.A. Whenever another user, for example, user B, wishes to send a message M to user A, user B obtains E.sub.A from the public file and encrypts the desired message M to form an encrypted message E.sub.A (M). User B then sends the encrypted message to user A, who decrypts the message by computing D.sub.A (E.sub.A (M))=M. Since D.sub.A is not derivable from E.sub.A in a practical way, only user A can decrypt the message E.sub.A (M) sent by user B. User A can send a response back to user B by encrypting the response message using user B's encryption key E.sub.B, also available in the public file.
The above technique is useful where it is desired that only one recipient be able to read and understand the message. In an authentication mechanism, on the other hand, it is important only that no one but the particular sender can create the encrypted message. In this case, user B would encrypt the desired message using user B's own private key D.sub.B and the recipient user A would decrypt it using user B's public key E.sub.B obtained from the public file. Note that as used herein, because of the complementary nature between many public/private key pairs, it will be understood that the term "encryption" and "decryption" indicate complementary activities merely with respect to each other. That is, as used herein, a message may be recovered from its "encrypted" form by "decrypting" it, and a message may also be recovered from its "decrypted" form by "encrypting it". The terms "encrypted" and "decrypted" are not intended to imply anything about the readability of an encrypted or decrypted message.
One well known public key cryptosystem is sponsored by RSA Data Security, Inc., Redwood City, Calif. According to the RSA technique, a digital signature is created by first passing the desired message through a known message digesting algorithm to form a digest for the message. A digest is an item of data which is derived from the message but is much shorter than the message itself. Since it is much shorter than the message itself, the same digest will be produced by many different possible messages in the overall message space. However, the message digesting algorithm is chosen so that if the message is altered in any way, it is extremely difficult to determine what further modification is required to the message in order to produce the same digest. Once the digest is created, it is encrypted according to the sender's private key. The sender then transfers the encrypted digest in conjunction with the sender's public key and the desired message to the recipient.
In order to verify the authenticity of the message, the recipient separately passes the message through the known message digest algorithm produce a verification digest. The recipient also decrypts the sender's encrypted digest using the sender's public key. In this manner, the recipient produces a decrypted digest which is then compared with the verification digest. If the two digests match, assuming the sender is the only entity who was able to use the sender's private key, the recipient has verified that the message did in fact originate from the sender and that it has not been altered in any way.
One possible way of subverting this technique is that an impostor might modify the message, create a new digest, encrypt it according to a different private key, and send the message on to the recipient with the new encrypted digest and with the public key corresponding to the impostor's private key. Assuming the recipient relies on the public key received with the message in order to verify the authenticity of the message, then the recipient's verification that the message originated from the original sender will be false.
The recipient can avoid this problem by obtaining the sender's public key from a separate source rather than relying on the public key received with the message. For example, if the sender and recipient have communicated before, the recipient may have the sender's public key from a prior communication. This can be problematical, however, especially if the recipient is to receive messages from more than one sender. In that case, the recipient must maintain a database of the public key associated with each possible sender. Such a database may be difficult to keep current if the recipient uses a stand-alone computer system.
Many larger organizations avoid this problem by maintaining a single database of the public keys associated with at least their own members, which may accessed over a network by their members. A corporation, for example, might maintain a network for its employees and maintain such a database on the network. In this manner, the recipient of a message can obtain the public key associated with the sender of the message from the central database, assuming the sender is a member of the organization. If either the sender of a message or the recipient of a message are not members of an organization which maintains such a database, or if the recipient in a particular instance does not have access to the database, then the recipient may be able to dial into a central database which is maintained for several different organizations to obtain the sender's public key.
This technique for verifying a sender's public key is typically useful only by recipients who are members of such larger organizations, or who pay a fee for modem access to a centralized database. A stand-alone user is usually excluded from this type of verification. In addition, even members of large organizations are excluded from this scheme if they are temporarily out of touch with their network, such as when they are using a portable computer on travel.
According to the RSA mechanism, a sender can prevent subversion of the authentication technique by transferring the original message and encrypted digest in conjunction with what is known as a certificate. To create the certificate, the sender passes the sender's public key through the message digesting algorithm to form a digest for the sender's public key, which is then encrypted by a third party certifier using the certifier's private key to form an encrypted digest of the sender's public key. The certifier may be any third party who is trusted by the recipient to not be subject to subversion by the impostor. The sender then transmits to the recipient the original desired message, the encrypted digest for the original message, and the certificate (including the sender's public key and the encrypted digest of the sender's public key). As with the non-certificated transmission, the sender may include the certifier's public key as part of the certificate. (Note that the sender does not actually need access to the certifier for each message; the certifier can encrypt the digest of the sender's public key once, and the sender can keep that encrypted digest locally for building all future certificates.)
In order to verify the authenticity of the message, the recipient uses the sender's public key, from the certificate, to verify the authenticity of the message itself in the manner described above. The recipient also uses the certifier's public key to verify the authenticity of the encrypted digest in the certificate of the sender's public key.
But the RSA certification scheme is also subject to subversion in the same manner as the non-certificated scheme if the recipient still must rely on the validity of the certifier's public key as provided in the certificate to determine the authenticity of the certificate itself. Both the uncertificated and the certificated transmission schemes sponsored by RSA, therefore, require that at some point, for maximum certainty of the authenticity of a received message, the recipient must know the public key of either the sender or of the certifier from a different source. As mentioned, however, that requirement tends to exclude many possible users.
In the RSA certification scheme, the most trusted third party is defined to be RSA Data Security, Inc. itself, or entities authorized by RSA Data Security, Inc. to use RSA's own private key (such as, possibly, employees or a key administering entity). Thus, whereas an ordinary sender of a message might use a first organization in which he is a member to certify his messages, that first organization might use a second organization to certify messages originated by the first organization. The second organization might then use RSA Data Security, Inc. itself to certify messages originated by the second organization. As long as the RSA private key remains secret, messages certified using the RSA private key are typically considered beyond subversion since the RSA public key is widely available from many sources. And since RSA is the nearest thing to a central certifier, an ordinary user-recipient of messages might download RSA;s public key once and keep it locally to verify any message which was certified using the RSA private key. The user need not rely on the RSA public key ostensibly transmitted with the message. However, this technique is also inadequate since most messages are not certified by RSA. Thus users are still undesirably excluded from the RSA cryptosystem.
The reasons set forth above which exclude recipients from the RSA cryptosystem, also tend to exclude senders of certificated messages if they use more than one certifier or if they frequently change public/private key pairs. If a sender uses more than one certifier for different messages, then the sender either needs to maintain a database of certificates, which could become outdated, or needs access to each certifier, which again usually requires membership in a large organization and connectability to the organization's network. If the sender frequently changes public/private key pairs, then the sender needs access to the certifier in order to have each new public key certified.
Separately, graphical user interfaces on computer systems are gaining widespread use. Typical systems include the Macintosh Finder.TM. environment in Macintosh computers provided by Apple Computer, Inc., Cupertino, Calif.; the Windows.TM. environment provided by Microsoft Corporation, Redmond, Wash.; and the New Wave.TM. environment provided by Hewlett-Packard, Palo Alto, Calif. In such systems, a workspace on the display system is set up with a desktop metaphor. Within the desktop, there are a number of icons displayed which correspond to objects stored in memory. The objects include, for instance, files, applications programs, control panels, and enclosures that enclose other objects. Opening an icon results in display of a window within the desktop corresponding to the underlying object. Thus, opening an application window, such as a word processor, results in display of a document into which text may be entered using the word processing program. Opening of a control panel icon results in opening of a control panel window by which the user controls system parameters. Opening of an enclosure icon, such as a folder in the Macintosh Finder.TM. environment, results in opening of a window that encloses other icons.
In the Macintosh Finder.TM. environment, each object includes a header specifying a four-byte object type and a four-byte creator. The file type field specifies, among other things, whether the object is a data file, an application program, a control panel, or an enclosure that encloses other objects.
The computer system is typically equipped with a pointing device such as a mouse and a pushbutton. When the user desires to select an object, the user first uses the mouse to position a cursor over the desired object, and then clicks the pushbutton once. The computer system changes the display of the icon corresponding to the selected object in some manner, such as by reverse video, to indicate that the object has been selected. To open an object, the user can first select the desired object and then select a control indicator entitled "open". Alternatively, the user can double-click on the desired icon. In either case, the computer system includes logic (including software) which determines the object type and creator, and performs the necessary steps to "open" the object. If the object type is "document", for example, and the creator is a word processor application program, then the computer system will invoke the application program and cause it to load in the selected document for editing. If the object type is "application program", then the computer system will invoke the application without any user-selected initial data.
Another behavior which a user can perform in the Macintosh Finder.TM. environment is known as "drag-and-drop". In this behavior, the user uses the pointing device to position the cursor over a first desired icon, presses the button, and before releasing it, uses the pointing device to "drag" the first icon to a second desired icon. The user then releases the pushbutton. In this manner, the user has selected two objects. If the first object is a data file and the second object is an enclosure which encloses other objects, such as a folder, the computer system will move the first selected object into the enclosure. If the second selected object is an application program, the computer system will invoke the application program and attempt to supply it with the first selected object as input or initial data. In this manner, a data file created using one application program may be easily brought into a second application program. For example, if the first selected object is a document created by a first word processor, and the second selected object is a second word processor application program, then the second word processor may attempt to convert the document from the format of the first word processor to the format of the second word processor before making it available for editing. The second word processor determines the creator of the input document from the creator field in the header of the input document.
Despite the ease with which a graphical user interface is used, and despite its familiarity to a large number of users, no easy way of signing documents, appending a certificate, or verifying documents, is known which takes advantage of the interface.
Accordingly, there is a strong need for improved techniques for signing and certifying documents and for verifying documents to ensure that they did in fact from the stated source, and that they have not been tampered with en route.